import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class hmwk3 {

	
	
	public static Hashtable<Integer, String> bucket = new Hashtable();	
	public static ArrayList<String> candidates = new ArrayList();
	public static double min_support = 0.4;
	public static double min_confidence = 0.6;
	public static TreeSet<String> one_pass = new TreeSet();
	public static ArrayList<String> two_pass = new ArrayList();
	public static ArrayList<String> two_pass_after = new ArrayList();
	public static ArrayList<String> largeItems= new ArrayList();
	public static ArrayList<String> templist1 = new ArrayList();
	public static ArrayList<String> templist2 = new ArrayList();
	public static Hashtable<String, Double> associates_rule = new Hashtable();

	
	public static void main(String args[]) throws IOException{
		

		set();
		System.out.println("bucket: "+bucket);
		
		getOnePass();
		System.out.println("one_pass: "+one_pass);
		
		if(one_pass.size()!=0){
			largeItems.addAll(one_pass);
			templist1.addAll(one_pass);
			templist2.addAll(templist1);
			
			getTwoPass(templist1, templist2);
		}
		
		//sort every transaction in two_pass
		String[] msg;
		Iterator iterator1 = two_pass.iterator();
		while(iterator1.hasNext()){
			msg = iterator1.next().toString().split(" ");
			TreeSet<String> tree = new TreeSet();
			for(int i=0;i<msg.length;i++){
				String word1 = msg[i];
				tree.add(word1);
			}
			Iterator iterator2 = tree.iterator();
			String msg1 = "";
			while(iterator2.hasNext()){
				String word2 = iterator2.next().toString();
				msg1 = msg1+" "+ word2;
			}
			two_pass_after.add(msg1);
		}
		System.out.println("two_pass_after: "+two_pass_after);
		
		
		if(two_pass_after.size()!=0){
			largeItems.addAll(two_pass_after);
			templist1.clear();
			templist2.clear();
			templist1.addAll(two_pass_after);
			templist2.addAll(templist1);
			
			ArrayList<String> array = new ArrayList(); 
			//round = round+1;
			array = getGeneralPass(templist1, templist2);  //array=general_pass
			
			
			largeItems.addAll(array);
			while(!array.isEmpty()){
				templist1.clear();
				templist2.clear();
				templist1.addAll(array);
				templist2.addAll(templist1);
				//round = round+1;
				array = getGeneralPass(templist1, templist2);
				largeItems.addAll(array);
			}

		}
		
		System.out.println("largeItems: "+largeItems);
		getAssociatesRule();
		System.out.println("There are "+ associates_rule.size() + " associates rules.");
		System.out.println("associates_rule: "+associates_rule);

	}	
	
    public static void set(){
    	String items0 = "pen"+" "+"diary"+" "+"soap"+" "+"milk"+" "+"water";
    	String items1 = "pen"+" "+"ink"+" "+"diary";
    	String items2 = "pen"+" "+"diary"+" "+"water";
    	String items3 = "ink"+" "+"diary"+" "+"soap"+" "+"water"+" "+"milk";
    	String items4 = "pen"+" "+"soap"+" "+"water";
    	
    	bucket.put(0, items0);
    	bucket.put(1, items1);
    	bucket.put(2, items2);
    	bucket.put(3, items3);
    	bucket.put(4, items4);

    
    }
    
    public static void getOnePass(){
    	String[] tmp;
    	String transaction;
    	String item;
    	
    	
    	//get candidates for first pass
    	Iterator it1 = bucket.values().iterator();
    	while(it1.hasNext()){
    		tmp = it1.next().toString().split(" ");
    		for (int i = 0; i<tmp.length;i++){
    			item = tmp[i];
    			if (!candidates.contains(item)){
    				candidates.add(item);
    			}
    			else{
    				continue;
    			}
    		}
    	}
    	System.out.println("one_candidates: "+candidates);
    	
    	//get one_pass large itemsets
    	//int round = 1;
    	Iterator it2 = candidates.iterator();
    	while(it2.hasNext()){
        	
    		double count = 0;
    		String temp_candidate = it2.next().toString();
        	
    		Iterator it3 = bucket.values().iterator();
    		while(it3.hasNext()){
    		    transaction = it3.next().toString();
    		    //System.out.println(transaction);
    			if(transaction.contains(temp_candidate)){
    				count = count + 1;
    			}
    			else {
    				continue;
    			}
    		}
    		//System.out.println(count);
    		double final_count = count/(bucket.size());
    		//System.out.println(final_count);
    		if (final_count >= min_support){
    			one_pass.add(temp_candidate);
    		}
    		else{
    			continue;
    		}
    	}
    }

   
    public static void getTwoPass(ArrayList<String> list1, ArrayList<String> list2){
    	
    	ArrayList<String> two_candidates = new ArrayList();
    	//get candidates for second pass
    	Iterator it4 = list1.iterator();
    	while(it4.hasNext()){
    		String item = it4.next().toString();
    		String new_largeitems;
    		int m = list1.indexOf(item);
    		for (int index = m+1; index < list2.size(); index++){
    			new_largeitems = item+" "+list2.get(index);
    			two_candidates.add(new_largeitems);
    		}
    		
    	}
    	System.out.println("two_candidates: "+two_candidates);

    	//get large item sets for second pass
    	String[] str;
    	String items;
    	Iterator it5 = two_candidates.iterator();
    	while(it5.hasNext()){
    		double count = 0;
    		items = it5.next().toString();
    		str = items.split(" ");
    		
    		//System.out.println("items:"+items);
    		//System.out.println("str:"+str[0]+" "+str[1]);

    		Iterator it6 = bucket.values().iterator();
    		while(it6.hasNext()){
    			String transaction = it6.next().toString();
    			if((transaction.contains(str[0])) && (transaction.contains(str[1]))){
    				count = count+1;
    			}
    			else{
    				continue;
    			}
    		}//end while
    		//System.out.println(count);
    		double final_count = count/(bucket.size());
    		//System.out.println(final_count);
    		if(final_count >= min_support){
    			two_pass.add(items);
    		}//end if
    		else{
    			continue;
    		}
    	}//end while
    }
    
    
    public static ArrayList<String> getGeneralPass(ArrayList<String> list1, ArrayList<String> list2){
    	ArrayList<String> general_pass = new ArrayList();
    	HashSet<String> general_candidates = new HashSet();
    	HashSet<String> general_candidates_after = new HashSet();
    	String word1;
    	String word2;
    	
    	//get candidates for general pass
    	System.out.println("list1: "+list1);
    	System.out.println("list2: "+list2);
    	
    	Iterator it7 = list1.iterator();
    	String transactions1;
    	String[] transaction1;
    	while (it7.hasNext()){
    		transactions1 = it7.next().toString();
    		transaction1 = transactions1.split(" "); // for each row of list1 
    		ArrayList<String> temp_list1 = new ArrayList();
    		for(int m=0; m<transaction1.length; m++){
    			word1 = transaction1[m];
    			temp_list1.add(word1);
    		} // for each row of list1, store in temp_list1
    		
    		//Iterator it8 = list2.iterator();
    		int index1 = list1.indexOf(transactions1);
    		String transactions2;
    		String[] transaction2;
    		for(int index2=(index1+1); index2<list2.size(); index2++){
    		//while(it8.hasNext()){	
    			transactions2 = list2.get(index2);
    			transaction2 = transactions2.split(" ");// for each row of list2
    			ArrayList<String> temp_list2 = new ArrayList();
    			for(int n=0; n<transaction2.length; n++){
    				word2 = transaction2[n];
    				temp_list2.add(word2);
    			} // for each row of list2, store in temp_list2
    			
    			//check how many same words
    			String newitemsets = "";
    			Iterator it9 = temp_list1.iterator();
    			while(it9.hasNext()){
    				String msg = it9.next().toString();
    				if(temp_list2.contains(msg)){
    					temp_list2.remove(msg);
    					newitemsets = newitemsets + " " + msg;
    				}
    				else{
    					newitemsets = newitemsets + " " + msg;
    					continue;
    				}
    			}
    			
    			if(temp_list2.size()==1){
    				String extra_word = temp_list2.get(0);
    				newitemsets = newitemsets + " " + extra_word;
    				general_candidates.add(newitemsets);
    			}
    			else{
    				continue;
    			}
    		}
    		
    	}
    	//System.out.println("general_candidates: "+general_candidates);
    	//sort
    	String[] message;
		Iterator iterator1 = general_candidates.iterator();
		while(iterator1.hasNext()){
			message = iterator1.next().toString().split(" ");
			TreeSet<String> tree = new TreeSet();
			for(int i=0;i<message.length;i++){
				String wordterm1 = message[i];
				tree.add(wordterm1);
			}
			Iterator iterator2 = tree.iterator();
			String message1 = "";
			while(iterator2.hasNext()){
				String wordterm2 = iterator2.next().toString();
				message1 = message1+" "+ wordterm2;
			}
			general_candidates_after.add(message1);
		}
    	System.out.println("general_candidates_after: "+general_candidates_after);

    	
    	
    	//get large itemsets for general pass
    	Iterator it = general_candidates_after.iterator();
    	while(it.hasNext()){
    		String items = it.next().toString();  // for each row in candidates set
    		String[] str = items.split(" ");
    		int len = str.length;
    		double count=0;
    		Iterator its = bucket.values().iterator();
    		while(its.hasNext()){
    			String transaction = its.next().toString(); // for each transaction in bucket
    			boolean flag = true;
    			for (int m=0; m<len; m++){
    				if(!transaction.contains(str[m])){
    					flag =false;
    					break;
    				}
    				else{
    					continue;
    				}
    			}
    			if(flag){
    				count = count +1;
    			}
    		}
    		double final_count = count/(bucket.size());
    		if(final_count >= min_support){
    			general_pass.add(items);
    		}
    		else{
    			continue;
    		}
    	}
    	
    	System.out.println("general_pass: "+general_pass);
    	
    	
    	
    	return general_pass;
    	
    }
    

    
    public static void getAssociatesRule(){
    	
    	String candidates_rule = "";
    	String[] candidates_rule_str;
    	Iterator it1 = largeItems.iterator();
    	while(it1.hasNext()){
    		candidates_rule = it1.next().toString(); //for each large item transaction
    		candidates_rule_str = candidates_rule.split(" ");
    		int length = candidates_rule_str.length;
    		
    		if(length == 1){
    			continue;
    		}
    		else{
    			for(int m=0;m<length;m++){
    				double sup_LHS = 0;
    				double sup_both = 0;
    				ArrayList<String> temp = new ArrayList();
    	    		for(int i =0;i<length;i++){
    	    			temp.add(candidates_rule_str[i]); //store all items of this transaction in temp
    	    		}
    	    		System.out.println("temp_total: "+temp);
    				
    				if(candidates_rule_str[m].isEmpty()){
    					continue;
    				}
    				else{
	    				String RHS = candidates_rule_str[m]; //for each word in this transaction, set it as RHS
	    				System.out.println("RHS: "+RHS);
	    				
	    				// calculate sup_both
	    				Iterator it2 = bucket.values().iterator();
	    				while(it2.hasNext()){
	    					String this_tran1 = it2.next().toString();
	    					boolean flag1 = true;
	    					Iterator it3 = temp.iterator();
	    					while(it3.hasNext()){                                  //for each item in this transaction
	    						if(this_tran1.contains(it3.next().toString())){
	    							continue;
	    						}
	    						else{
	    							flag1 = false;
	    							break;
	    						}
	    					}
	    					if(flag1){
	    						sup_both = sup_both + 1;
	    					}
	    					else{
	    						continue;
	    					}
	    				}
	   				
	    				//calculate sup_LHS
	    				temp.remove(RHS); // temp stores all items in LHS
	    				System.out.println("temp_after: "+temp);
	    				Iterator it4 = bucket.values().iterator();
	    				while(it4.hasNext()){
	    					String this_tran2 = it4.next().toString(); //for each transaction
	    					boolean flag2 = true;
	    					Iterator it5 = temp.iterator();
	    					while(it5.hasNext()){								   //for each item in this transacion
	    						if(this_tran2.contains(it5.next().toString())){
	    							continue;
	    						}
	    						else{
	    							flag2 = false;
	    							break; // to next transaction
	    						}
	    					}
	    					if(flag2){
	    						sup_LHS = sup_LHS + 1;
	    					}
	    					else{
	    						continue; //to next transaction
	    					}
	    				} // end while
	    				
	    				double confidence = sup_both/sup_LHS;
	    				if(confidence >= min_confidence){
	    					String tmp = "";
	    					Iterator it6 = temp.iterator();
	    					while(it6.hasNext()){
	    						tmp = tmp + " " + it6.next().toString();
	    					}
	    					String rule = tmp + " ==> " + RHS;
	    					associates_rule.put(rule,confidence);
	    				}
	    				else{
	    					continue;
	    				}
    				}
    			} // end for
    		} // end else
    	} // end while
    } 
    
    
}

